package ch3.section3;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * remove方法对LinkedList类的使用。
 * 将一个表中所有具有偶数值的项删除。
 */
public class example1 {

    public static void main(String[] args) {
        LinkedList<Integer> links = new LinkedList<>();
        ArrayList<Integer> arrays = new ArrayList<>();
        for (int i = 0;i<40000;i++){
            links.add(i);
            arrays.add(i);
        }
        System.out.println("before:"+links);
        long start = System.currentTimeMillis();
//        removeEvensVer1(links); //花费时间：1125ms
//        removeEvensVer1(arrays);//花费时间：39ms

//        removeEvensVer3(links); //花费时间：3ms
        removeEvensVer3(arrays); //花费时间：42ms
        System.out.println("花费时间："+(System.currentTimeMillis() - start)+"ms");
        System.out.println("after:"+links);

    }

    /**
     * 算法对所有的类型的表都是二次的。
     * ArrayList:remove()效率不高
     * LinkedList:get()效率不高
     * @param lst
     */
    public static void removeEvensVer1(List<Integer> lst){
        int i = 0;
        while (i < lst.size()){
            if(lst.get(i) % 2 == 0){
                lst.remove(i);
            }else {
                i++;
            }
        }
    }

    /**
     * 会报错
     * @param lst
     */
    public static void removeEvensVer2(List<Integer> lst){
        for(Integer x : lst){
            if(x % 2 == 0){
                lst.remove(x);
            }
        }
    }

    /**
     * 该方法，在迭代器找到一个偶数值项之后，我们可以使用该迭代器来删除这个它刚看到的值。对于一个LinkedList
     * 对该迭代器的remove方法的调用只花费常数时间，因为迭代器位于需要被删除的节点。
     * @param lst
     */
    public static void removeEvensVer3(List<Integer> lst){
        Iterator<Integer> itr = lst.iterator();
        while (itr.hasNext()){
            if(itr.next() % 2 == 0){
                itr.remove();
            }
        }
    }
}
